package com.xn.coursed.service.impl;

import com.xn.coursed.commen.GraphUtil;
import com.xn.coursed.pojo.entity.Graph;
import com.xn.coursed.service.MapService;
import com.xn.coursed.pojo.dto.MapDTO;
import org.springframework.beans.factory.annotation.Autowired;
import org.springframework.stereotype.Service;

import java.util.*;

@Service
public class MapServiceImpl implements MapService {
    private Graph graph;
    @Autowired
    private GraphUtil graphUtil;

    public Map<String, String> getDistance(MapDTO mapDTO) {
        //      哈希图用于返回数据
        HashMap<String, String> map = new HashMap<>();
        //      初始化图
        graph=graphUtil.init();
        if (graph == null) {
            map.put("error", "图初始化失败");
            return map;
        }
//      获得起点和终点
        String Location1 = mapDTO.getLocation1();
        String Location2 = mapDTO.getLocation2();
        int start=getIndex(Location1);
        int destination=getIndex(Location2);
        if (start==-1||destination==-1){
            System.out.println("异常！！！！！！！！！！！！！！");
            return null;
        }


        graph.getDist()[start]=0;


        boolean[] processed = new boolean[graph.getVexNum()];

        for (int i = 0; i < graph.getVexNum(); i++) {
            int u = find_min_distanceNode(processed);
            if (u == -1) break;
            processed[u] = true;
            for (int v = 0; v < graph.getVexNum(); v++) {
                if (!processed[v] && graph.getArc()[u][v] != 0 && graph.getDist()[u] != Integer.MAX_VALUE) {
                    int newDist = graph.getDist()[u] + graph.getArc()[u][v];
                    if (newDist < graph.getDist()[v]) {
                        graph.getDist()[v] = newDist;
                        graph.getPreIndex()[v] = u;
                    }
                }
            }
        }

        String path=printShortestPath(destination);
        map.put("message",path);

        return map;
    }
    private int find_min_distanceNode( boolean[] processed) {
        int minDist = Integer.MAX_VALUE;
        int minIndex = -1;
        for (int i = 0; i < graph.getVexNum(); i++) {
            if (!processed[i] && graph.getDist()[i] < minDist) {
                minDist = graph.getDist()[i];
                minIndex = i;
            }
        }
        return minIndex;
    }
    private int getIndex(String location){
        for (int i=0;i<graph.getVexNum();i++){
            if (graph.getVex()[i].equals(location)){
                return i;
            }
        }
        return -1;
    }
    public String printShortestPath(int end) {
        if (graph.getDist()[end] == Integer.MAX_VALUE) {
            System.out.println("没有可行路径");
            return null;
        }

        StringBuilder PATH= new StringBuilder();
        List<Integer> path = new ArrayList<>();
        for (int at = end; at != -1; at = graph.getPreIndex()[at]) {
            path.add(at);
        }
        Collections.reverse(path);

        System.out.print("最短路径：");
        for (int i = 0; i < path.size(); i++) {
            if (i > 0) PATH.append(" → ");
            PATH.append(graph.getVex()[path.get(i)]);
            System.out.print(graph.getVex()[path.get(i)]);
            if (i != path.size() - 1) System.out.print(" → ");
        }
        PATH.append("  最短距离为："+graph.getDist()[end]);
        return PATH.toString();
    }
}
